The invention presents a new method for high performance hardware circuit pipelining; by using the said dynamic pipelining method, it is capable of enabling variant-iteration-execution-time circuits in run-time determined latencies to achieve the optimal pipeline speed.
Getting a higher performance is one of the most important goals of designing Application Specific Integrated Circuits (ASIC""s). The action of an ASIC often contains the time-consuming loops. To optimize the performance efficiently, the parallelism hidden in the repetitive loops must be located, and then pipelined. In the past, many pipelining techniques have been developed to explore the parallelism of loops in an ASIC. Functional pipelining, proposed by many people such as E. M. Circzyc (in the Proc. of the International Symposium Circuits and Systems(ISCAS), pp. 382-385, in 1987.), is used to pipeline the execution of the loop with acyclic iterations. On the other hand, loop pipelining or software pipelining, such as the methods revealed by A. Aiken et. al. (in Proc. ACM SIGPLAN""88 Conf. on Prog. Lang. Design and Implementation, 1988.) and by M. Lam (in Proc. ACM SIGPLAN""88 Conf on Prog. Lang. Design and Implementation, pp.318-328, 1988.), is applied to explore the parallelism across iterations of the loop with cyclic iterations. Structured pipeline uses the pipelined functional units to prompt the ASIC performance. Other approaches such as that proposed by J. P. Sheu, et. al. (in IEEE Trans. on Parallel and Distributed Systems, Vol. 2, No. 3, July 1991.) have been proposed to find the potential parallelism of nested loops. In addition, many patents have proposed different pipelining methods for enhancing circuit performance such as U.S. Pat. Nos: 4,677,549, 4,742,453, 5,079,736, 5,428,756, and 5,684,422. However, these approaches might handle only nested loops with constant loop-iteration numbers and the execution time of each iteration in them is fixed.
For a pipeline design, consecutive two iterations of a loop are initiated at a time interval called latency. In existing pipelining techniques, the latencies of a pipeline are all set as a fixed value or some fixed values. However, in the loops of many ASICs, variant iteration execution time and time-relative data dependencies between different iterations make them to be impossibly or inefficiently pipelined, because the values of the pipeline latencies cannot be fixed and be known in advance. To solve such problems, the fixed latency assumption must be removed and more flexibility is needed. Here, a new pipeline design approach for high performance ASICs, called dynamic pipelining, is invented to pipelinely designing those ASIC loops using variant latencies efficiently.
The invention is even more suitable for the circuit""s loops with the factor of inconsistent execution time for each iteration and/or the number of iterations unfixed. The traditional pipelining approach cannot resolve such problems, while by using the variant latencies pipeline of the invention, the pipelining of time-variant loops and then time-efficiency of the circuit can be successfully achieved.
Moreover, the cost of hardware using the proposed design method is at the same class as that of the traditional pipelining design: it would increase the quantity of state registers, certain hardware components as well as the complexity of its control circuit. The amount of these increased hardware components varies according to the different designs, and cannot be quantitatively explained. Despite which, it is generally acceptable just as the design of conventional pipelining has been, which could be seen from the results of our empirical study.
The object of the invention is to expose a new type of pipelining method applicable for high performance digital circuits. By using the said dynamic pipelining method, it can effectively pipeline circuits of time-variant loops in run-time determined latencies to achieve the goal the optimal pipeline speed.
In addition, the invention further proposes a coordinated type of controller for the dynamic pipelined circuit, which consists of two coordinated finite state machines and enables the dynamic pipelined datapath to execute at variant latencies.
All those acquainted with the skill of pipelining will undoubtedly be very clear of the objective and advantages revealed by the invention after the going over the explanation and the examples cited in the following along with the drawings.